package LeedCode_BinaryTree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:后序非递归遍历
 * User: 阿宾
 * Date: 2024-12-05
 * Time: 10:17
 */
public class Demo14 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tag = null;//指向上一个访问过的结点
        while (root != null || !stack.empty()){
            while (root != null){
                stack.push(root);
                root = root.left;
            }
            TreeNode tmp = stack.peek();
            if(tmp.right != null && tmp.right != tag){
                root = tmp.right;
            }else {
                //此时左右子树都为空，并且这个结点没有被访问
                list.add(tmp.val);
                stack.pop();
                tag = tmp;
            }
            /*if(root != null){
                stack.push(root);
                root = root.left;
            }else {
                //左子树为空，要判断右子树是否为空
                TreeNode tmp = stack.peek();
                if(tmp.right != null && tmp.right != tag){
                    root = tmp.right;
                }else {
                    //此时左右子树都为空，并且这个结点没有被访问
                    list.add(tmp.val);
                    stack.pop();
                    tag = tmp;
                    root = null;
                }
            }*/
        }
        return list;
    }
}
